The number of elements in a set is called its cardinality and is denoted by . For example, the set has a cadinality equal to 4. Some sets like this one have a finite number of elements, but others, such as the set of all natural numbers, do not. The latter are called infinite sets.

If a set contains more than a single copy of one of its elements, the additional copies are not taken into account. For example, $\{1,2,3,4,1,5,2\}$ is mathematically considered the exact same set as $\{1,2,3,4,5\}$ and so the size of both sets is 5.
Copy

The union of two sets, denoted by , is a set which contains all the elements from and . For example,

The intersection of two sets, denoted by , is a set which contains only the elements which are found in both and . For example,

If the two sets have no elements in common, then their intersection is the empty set $\emptyset$.
Copy

The relative complement of a set with respect to another set , denoted by , is the set obtained by removing from all of its elements that are also found in . For example,

A string is a sequence of characters. The set of characters that we can choose from to make our string is called an alphabet and is usually denoted by . For example, if , then some valid strings over that alphabet will be abcd, ac,acd,c, etc.

The set of all strings with a certain length over some alphabet is denoted by . For example, the set of 2-letter strings which we can make from is

If we wanted to denote the set of all possible strings of any finite length over a given alphabet , then we would write or, for our example, . This would be the set of all strings which can be written with the letter a,b,c and d such as ab or aaccdba.

- the empty string "" which has no characters and can be constructed with any alphabet
- binary strings $\{0,1\}^*$ - strings which only contain 0s and 1s
Copy

A function definition describes what the function outputs given a particular input and has the syntax

The expression can be a mathematical formula, it can be a sentence explaining what the function does, or it can be a mixture of both.

The function $f: \mathbb{R} \to \mathbb{R}$ which returns the square of its input would be defined as follows:

$$f(x) \coloneqq x^2$$

The $x$ is just an arbitrary placeholder for the argument - we could have very well used $y$ or a word or anything we would like.

The function $PALINDROME: \{0,1\}^* \to \{0,1\}$ is the function which outputs 1 if its input is a palindrome string and outputs 0 otherwise. This was an example of a definition with a sentence.
Copy

Functions can also be piecewise-defined. This is when the function does different things depending on whether its input satisfies a given condition. For example, the function can be defined as:

The absolute value function is also piecewise-defined:

Finally, a function can be specified by a table listing all its inputs and their corresponding outputs. For example,

This does not give us a very good idea of what the function is actually supposed to do, but it certainly is a way to define it.

A function need not be defined for all values in its domain. For example, the division function $DIV: \mathbb{R} \times \mathbb{R} \to \mathbb{R}$, or alternatively $DIV(a,b) = \frac{a}{b}$, is not defined for $b = 0$ because one cannot divide by 0. Such functions are called *partial* and the set of all values for which the function is actually defined is called its *natural domain*. This can be seen from the following diagram for a function $f: X \to Y$:

![](Resources/Images/Function%20Domain.svg)

The domain is $X$, while the natural domain is $\{x_1,x_2,x_3,...\} \subset X$. A function which is defined for *all* values in its domain is called a *total* function.
Copy

These are terms which describe the relationship a function establishes between its input sets and its output sets.

An *injective* function, or one-to-one function, is a function which given two different inputs, will always produce two different outputs - every element in its input sets is mapped to a single element from its output sets. An example of such a function is $f(x) = x + 1$ - there are no two inputs $x \ne x'$ for which $f(x) = f(x')$. However, the function $g(x) = x^2$ is *not* an  injection because opposite numbers produce the same output, i.e. $g(2) = g(-2) = 4$.

A *surjective* function is a function which covers its entire codomain. For example, $f: \mathbb{R} \to \mathbb{R}$ with $f(x) = x + 1$ is a surjection because every real number can be produced from it, i.e. for every $y \in \mathbb{R}$ there is at least one number $x$ such that $f(x) = y$. Contrastingly, the absolute value function $||: \mathbb{R} \to \mathbb{R}$ is *not* surjective because it cannot produce negative values. The subset of the codomain which contains all values which can be obtained from the function is called the function's *image*.

A *bijective* function, also known as a one-to-one map or one-to-one correspondence, is a function which is both surjective and injective, i.e. it covers its entire codomain and assigns to every element it in it, only *one* element from its natural domain.

![](Resources/Images/Injection,%20Surjection,%20Bijection.svg)

Copy

There are a few functions used extensively throughout cryptography and computer science. Although they are defined on single bits, every one of them can be extended to binary strings simply by applying the function on a bit-by-bit basis.

A function $\mu :\mathbb{N} \to [0,1]$ is *negligible* if for every polynomial $p: \mathbb{N} \to \mathbb{N}$ there exists a number $N \in \mathbb{N}$ such that $\mu(n) \lt \frac{1}{p(n)}$ for every $n \gt N$.
Copy

The definition itself is not that important, just remember that a negligible function approaches 0 and it does so quickly as its input approaches infinity.

Essentially, a function is negligble if it approaches 0 as its input becomes larger and larger. That is, no matter how big a polynomial one can think of, after some input $N$ the function will always be smaller than the reciprocal of the polynomial. 

The reason the function outputs a number between 0 and 1 is that such functions are usually used in the context of probabilities (as is the case here).
Copy

The reason we want the negligible function to get smaller and smaller as its input gets larger and larger is because we are using the key length for its input, so we want to say that longer keys are still more secure than shorter ones but at the same time we do not need to use massive keys. By today's standards, a reasonable negligible function would be one which is already on the order of for an input . So, not only does the function need to approach 0, but it also needs to do so fairly quickly.